Comes down to the smallest cut.

Issue List

The Problem of Finding the Best Choice

Typical pattern

Paint a 100 x 100 grid in two colors.

There are about 100 options for two choices.

The cost and rewards will depend on that choice.

There is a dependency between choices.

Represent the selection with a two-color fill of the vertex.

We call these paint colors S and T.

Introduce two apex starts and a goal

These are painted with S and T, respectively.

The vertices themselves are sometimes represented as S and T. I use start and goal in the code, and S and T in the diagram.

If it's a two-choice option, it's a natural response.

The basic form of the minimum cut is "if the color of both ends of a side is different, a cost will be incurred" and "we want to minimize the cost".

If you subtract an edge of weight x from vertex S to vertex v, it means "pay cost x if v is T".

If you subtract an edge of weight x from vertex v to vertex t, it means "pay cost x if v is S".

If it's a question of maximizing scores, make "score reduction" a cost.

Consider the case where all scores are obtained to be the offset, and the decrease from that offset to be the cost

I don't care that the edge values are negative in this phase, because I'll deal with that later.

Express the constraint "if vertex u is S, then vertex v is also S" by making the weight of edge uv sufficiently large

If we make it bidirectional, we get the expression u=v.

Once the graph is constructed, solve for the maximum flow

However, it does not correspond well with negative cost edges.

It becomes unintelligible around the negative capacity.

So we'll work on removing the negative edges here.

Note the vertex v to which the negative edge -x is connected

Vertex v color is either S or T

Make it cost an additional x either way.

Just add the additional cost of x to the sides Sv and vT

Now the negative side disappears.

This operation increases the offset by x

This "add x" does not have to be exactly x, so if you are not comfortable with exactly x, you can just give a large enough value as you see fit.

Once this is done, use an algorithm such as Dinic to find the maximum flow f from the start to the goal.

Just read cost as capacity.

The answer that offset - f seeks

---

But I'd prefer a problem I can solve with atcoder anyway.

+4 AOJ

---